#include "tools.cpp"

// leetcode 91
class Solution {
  public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        std::map<int, int> dp;
        return numDecodings(s, dp, 0);
    }

    int numDecodings(const string& s, std::map<int, int>& dp, int start) {
        if (s[start] == '0') return 0;
        if (start >= s.size()) return 1;
        if (dp.count(start) != 0) return dp[start];

        int result = 0;
        if (start + 1 < s.size() and ((s[start] == '2' and s[start + 1] <= '6') or (s[start] == '1')))
            result += numDecodings(s, dp, start + 2);
        result += numDecodings(s, dp, start + 1);
        dp[start] = result;
        return result;
    }

    int numDecodings(const string& s, int start) {
        if (s[start] == '0') return 0;
        if (start >= s.size()) return 1;

        int result = 0;
        if (start + 1 < s.size() and ((s[start] == '2' and s[start + 1] <= '6') or (s[start] == '1')))
            result += numDecodings(s, start + 2);
        result += numDecodings(s, start + 1);
        return result;
    }
};

int main() {
    std::string s{"12"};
    std::string ss{"231313124126"};
    Solution solu;
    std::cout << solu.numDecodings(s) << ", " << solu.numDecodings(ss) << std::endl;
    return 0;
}
